%skeleton "lalr1.cc" /* -*- C++ -*- */
%defines
%define parser_class_name "MAliceParser"

%locations

%initial-action {
	@$.begin.filename = @$.end.filename = &driver.getFileName();
};

%code requires { /* MAliceParser.hpp */

class MAliceDriver;
#include <MAlice/Ast/Ast.h>
#include <MAlice/Ast/ListAst.h>
#include <MAlice/Ast/TypeAst.h>
#include <MAlice/Ast/VariableAst.h>
#include <MAlice/Ast/StatementAst.h>
#include <MAlice/Ast/ExpressionAst.h>

#ifndef YYDEBUG
# ifdef NDEBUG
#  define YYDEBUG (0)
# else
#  define YYDEBUG (1)
# endif
#endif

}

%{ /* MAliceParser.cpp */

#include <sstream>
#include <tr1/unordered_set>

#include <MAlice/Codegen.h>

#include <MAlice/Ast/Ast.h>
#include <MAlice/Ast/ErrorAst.h>
#include <MAlice/Ast/ExpressionAst.h>
#include <MAlice/Ast/VoidExpressionAst.h>

#include <MAlice/Ast/CastBooleanAst.h>

#include <MAlice/Ast/IntegerLiteralAst.h>
#include <MAlice/Ast/CharacterLiteralAst.h>
#include <MAlice/Ast/FloatLiteralAst.h>
#include <MAlice/Ast/StringLiteralAst.h>

#include <MAlice/Ast/AssignmentOperatorAst.h>

#include <MAlice/Ast/UnaryAteOperatorAst.h>
#include <MAlice/Ast/UnaryDrankOperatorAst.h>
#include <MAlice/Ast/UnaryNegOperatorAst.h>
#include <MAlice/Ast/UnaryNotOperatorAst.h>

#include <MAlice/Ast/BinaryOperatorAst.h>
#include <MAlice/Ast/BinaryAddOperatorAst.h>
#include <MAlice/Ast/BinaryMulOperatorAst.h>
#include <MAlice/Ast/BinarySubOperatorAst.h>
#include <MAlice/Ast/BinaryDivOperatorAst.h>
#include <MAlice/Ast/BinaryModOperatorAst.h>
#include <MAlice/Ast/BinaryAndOperatorAst.h>
#include <MAlice/Ast/BinaryXorOperatorAst.h>
#include <MAlice/Ast/BinaryOrOperatorAst.h>

#include <MAlice/Ast/BinaryLessThanOperatorAst.h>
#include <MAlice/Ast/BinaryGreaterThanOperatorAst.h>
#include <MAlice/Ast/BinaryLessThanEqualOperatorAst.h>
#include <MAlice/Ast/BinaryGreaterThanEqualOperatorAst.h>
#include <MAlice/Ast/BinaryEqualityOperatorAst.h>
#include <MAlice/Ast/BinaryInEqualityOperatorAst.h>

#include <MAlice/Ast/ReturnExpressionAst.h>
#include <MAlice/Ast/VariableDeclAst.h>
#include <MAlice/Ast/PointerTypeAst.h>

#include <MAlice/Ast/FunctionCallAst.h>
#include <MAlice/Ast/FunctionProtoAst.h>
#include <MAlice/Ast/FunctionDeclAst.h>
#include <MAlice/Ast/FunctionParameterAst.h>

#include <MAlice/Ast/LookingGlassCallAst.h>
#include <MAlice/Ast/LookingGlassDeclAst.h>

#include <MAlice/Ast/EventuallyStatementAst.h>
#include <MAlice/Ast/ConditionalExpressionAst.h>
#include <MAlice/Ast/IfStatementAst.h>


#include <MAlice/Ast/ReadAst.h>
#include <MAlice/Ast/PrintAst.h>

#include <MAlice/MAliceDriver.hpp>

using namespace MAlice;

%}


%parse-param { MAliceDriver& driver }

%token     END              0 "End Of Line"


%token <s> id                 "id"
%token <s> array_id           "array_id"
%token <b> bool_literal       "bool"
%token <c> char_literal       "char"
%token <i> int_literal        "int"
%token <f> float_literal      "float"
%token <s> string_literal     "string"

%token <i> shift_left         "<<"
%token <i> shift_right        ">>"

%token <i> less_than_equal    "<="
%token <i> greater_than_equal ">="
%token <i> equal              "=="
%token <i> not_equal          "!="
%token <i> logical_and        "&&"
%token <i> logical_or         "||"

%token <s> kw_sentence 	"sentence"
%token <s> kw_number	"number"
%token <s> kw_letter 	"letter"

%token was_unsure

%token <i> kw_a      "a"
%token <i> kw_or     "or"
%token <i> kw_and    "and"
%token <i> kw_alice  "Alice"
%token <i> kw_became "became"
%token <i> kw_found  "found"
%token <i> kw_was    "was"
%token <i> kw_but    "but"
%token <i> kw_too    "too"
%token <i> kw_ate    "ate"
%token <i> kw_drank  "drank"
%token <i> kw_piece   "piece"
%token <i> kw_had     "had"
%token <i> kw_said    "said"
%token <i> kw_spoke   "spoke"
%token <i> kw_because "because" 
%token <i> kw_enough  "enough"
%token <i> kw_changed "changed"
%token <i> kw_times   "times"
%token <i> kw_unsure  "unsure" 
%token <i> kw_which   "which"
%token <i> kw_what    "what"
%token <i> kw_the     "The"
%token <i> kw_room    "room" 
%token <i> kw_perhaps "perhaps" 
%token <i> kw_either  "either" 
%token <i> kw_so      "so"
%token <i> kw_maybe   "maybe"
%token <i> kw_thought "thought"
%token <i> kw_then    "then"
%token <i> kw_spider  "spider"
%token <i> kw_went		"went"
%token <i> kw_through	"through"

%token <i> kw_eventually    "eventually"
%token <i> kw_contained     "contained"
%token <i> kw_looking_glass "Looking-Glass"


%union
{
	int                      i;
	double                   d;
	char                     c;
	bool                     b;
	string*                  s;
	::MAlice::Ast*           ast;
	::MAlice::ExpressionAst* expr;
	::MAlice::ListAst*       list;
	::MAlice::TypeAst*       type;
	::MAlice::VariableAst*   var;
};


%type <s>    type_name
%type <type> type_id
%type <expr> literal
%type <expr> primary_expr
%type <expr> unary_expr
%type <expr> multiplicative_expr
%type <expr> additive_expr		
%type <expr> shift_expr
%type <expr> relational_expr
%type <expr> equality_expr
%type <expr> and_expr
%type <expr> xor_expr
%type <expr> or_expr
%type <expr> logical_and_expr
%type <expr> logical_or_expr
%type <expr> base_expr

%type <var>  variable
%type <expr> decl
%type <expr> expr
%type <expr> fn_call

%type <ast>  either_expr

%type <expr> perhaps_expr
%type <ast>  perhaps
%type <ast>  perhaps_or
%type <list> perhaps_or_maybe



%type <list> fn_parameters
%type <list> fn_params_decl
%type <ast>  fn_proto
%type <ast>  fn_decl

%type <ast>  looking_glass

%type <ast>  stmt
%type <list> stmt_seq
%type <list> expr_stmt
%type <ast>  eventually_stmt

%type <ast>  program_token
%type <ast>  program

%destructor { delete $$; } <s>

%%

%start program;

literal
: "bool" {
	 $$ = new IntegerLiteralAst($<b>1 ? 1 : 0);
}
| "int" {
	 $$ = new IntegerLiteralAst($<i>1);
}
| "char" {
	 $$ = new CharacterLiteralAst($<c>1);
}
| "float" {
	 $$ = new FloatLiteralAst($<d>1);
}
| "string" {
	$$ = new StringLiteralAst(*$<s>1);
}
;

type_name
: "number" { 
	$$ = new string("number");
}
| "sentence" {
	$$ = new string("sentence");
}
| "letter" {
	$$ = new string("letter");
}
;

type_id
: type_name {
	$$ = new TypeAst( *$1 );
}
| "spider" type_name {
	$$ = new PointerTypeAst( *$2 );
}
;



variable
: id {
	$$ = new VariableAst( *$1 );
}
| array_id base_expr "piece" {
	$$ = new VariableAst( *$1, $2 );
}
;

fn_call
: id '(' fn_parameters ')' {
	// function call
	$$ = new FunctionCallAst( *$1, $3 );
}
;

primary_expr
: literal {
	$$ = $1;
}
| variable {
	$$ = $1;
}
| '(' base_expr ')' {
	$$ = $2;
} 
| fn_call {
	$$ = $1;
} 
;

unary_expr
: primary_expr {
	$$ = $1;
}
| '-' unary_expr {
	$$ = new UnaryNegOperatorAst($2);
}
| '+' unary_expr {
	$$ = $2;
}
| '~' unary_expr {
	$$ = new UnaryNotOperatorAst($2);
}
;

multiplicative_expr
: unary_expr {
	$$ = $1;
}
| multiplicative_expr '*' unary_expr {
	$$ = new BinaryMulOperatorAst($1, $3);
}
| multiplicative_expr '/' unary_expr {
	$$ = new BinaryDivOperatorAst($1, $3);
}
| multiplicative_expr '%' unary_expr {
	$$ = new BinaryModOperatorAst($1, $3);
}
;

additive_expr
: multiplicative_expr {
	$$ = $1;
}
| additive_expr '+' multiplicative_expr  {
	$$ = new BinaryAddOperatorAst($1, $3);
}
| additive_expr '-' multiplicative_expr {
	$$ = new BinarySubOperatorAst($1, $3);
}
;

shift_expr
: additive_expr {
	$$ = $1;
}
| shift_expr "<<" additive_expr {
	// $$ = new BinaryShiftLeftOperatorAst($1, $3);
	$$ = new ErrorAst( "NotImplemented" );
}
| shift_expr ">>" additive_expr {
	// $$ = new BinaryShiftRightOperatorAst($1, $3);
	$$ = new ErrorAst( "NotImplemented" );
}
;

relational_expr
: shift_expr {
	$$ = $1;
}
| relational_expr '<'  shift_expr {
	$$ = new BinaryLessThanOperatorAst($1, $3);
}
| relational_expr '>'  shift_expr {
	$$ = new BinaryGreaterThanOperatorAst($1, $3);
}
| relational_expr "<=" shift_expr {
	$$ = new BinaryLessThanEqualOperatorAst($1, $3);
}
| relational_expr ">=" shift_expr {
	$$ = new BinaryGreaterThanEqualOperatorAst($1, $3);
}
;

equality_expr
: relational_expr {	
	$$ = $1;
}
| equality_expr "==" relational_expr {
	$$ = new BinaryEqualityOperatorAst($1, $3);
}
| equality_expr "!=" relational_expr {
	$$ = new BinaryInEqualityOperatorAst($1, $3);
}
;

and_expr
: equality_expr {
	$$ = $1;
}
| and_expr '&' equality_expr {
	$$ = new BinaryAndOperatorAst($1, $3);
}
;

xor_expr
: and_expr {
	$$ = $1;
}
| xor_expr '^' and_expr {
	$$ = new BinaryXorOperatorAst($1, $3);
}
;

or_expr
: xor_expr {
	$$ = $1;
}
| or_expr '|' xor_expr {
	$$ = new BinaryOrOperatorAst($1, $3);
}
;

logical_and_expr
: or_expr {
	$$ = $1;
}
| logical_and_expr "&&" or_expr {
	$$ = new BinaryAndOperatorAst(new CastBooleanAst($1), new CastBooleanAst($3));
}
;

logical_or_expr
: logical_and_expr {
	$$ = $1;
}
| logical_or_expr "||" logical_and_expr {
	$$ = new BinaryOrOperatorAst(new CastBooleanAst($1), new CastBooleanAst($3));
}
;

base_expr
: logical_or_expr {
	$$ = $1;
}
;

decl
: id "was" "a" type_id {
	// XXX check $1 is a valid identifier, give warning if not
	assert ($1 != NULL && "NullPointer: id");
	$$ = new VariableDeclAst(*$1, $4, new IntegerLiteralAst(1));
}
| id "was" "a" type_id "too" {
	// XXX check $1 is a valid identifier, give warning if not
	assert ($1 != NULL && "NullPointer: id");
	$$ = new VariableDeclAst(*$1, $4, new IntegerLiteralAst(1));
}
| id "had" base_expr type_id {
	// dynamic array decleration
	$$ = new VariableDeclAst(*$1, $4, $3);
}
;

seperators
: "then" {}
| "and"  {}
| "but"  {}
| ','    {}
| '?'    {}
| '.'    {}
;

either_expr
: "either" '(' base_expr ')' "so" stmt_seq "or" stmt_seq was_unsure {
	ListAst* conditions = new ListAst();

	conditions->adopt(new ConditionalExpressionAst(new CastBooleanAst($3), 
										reinterpret_cast<StatementAst*>($6)));

	conditions->adopt(new ConditionalExpressionAst(new CastBooleanAst(new IntegerLiteralAst(1)), 
										reinterpret_cast<StatementAst*>($8)));

	$$ = new IfStatementAst(conditions);
}
;

perhaps_expr
: perhaps perhaps_or_maybe perhaps_or was_unsure {
	$$ = new IfStatementAst($2->adoptFirst($1)->adopt($3));
}
;

perhaps
: "perhaps" '(' base_expr ')' "so" stmt_seq {
	$$ = new ConditionalExpressionAst($3, reinterpret_cast<StatementAst*>($5));
}
;

 /* (or maybe ...)* */
perhaps_or_maybe
: /* empty */ {
	$$ = new ListAst();
}
| perhaps_or_maybe "or" "maybe" '(' base_expr ')' "so" stmt_seq {
	$$ = $1->adopt(
		new ConditionalExpressionAst($5, reinterpret_cast<StatementAst*>($8)));
}
;

perhaps_or
: /* empty */ {
	$$ = NULL;
}
| "or" stmt_seq {
	$$ = new ConditionalExpressionAst(
			new CastBooleanAst(new IntegerLiteralAst(1)), 
			reinterpret_cast<StatementAst*>($2));
}
;

expr
: decl {
	$$ = $1;
}
| variable "ate" {
	$$ = new UnaryAteOperatorAst($1);
}
| variable "drank" {
	$$ = new UnaryDrankOperatorAst($1);
}
| variable "became" base_expr {
	// assignment
	$$ = new AssignmentOperatorAst($1, $3);
}
| "Alice" "found" base_expr {
	$$ = new ReturnExpressionAst($3);
}
| base_expr "said" "Alice" {
	// print expression
	$$ = new PrintAst( $1 );
}
| string_literal "thought" "Alice" {
	// this is a comment, just ignore 
	$$ = VoidExpressionAst::get();
}
| base_expr "spoke" {
	// print expression
	$$ = new PrintAst( $1 );
}
| "what" "was" variable {
	// read 
	$$ = new ReadAst($3);
}
| variable "went" "through" id {
	// $1 needs to be a declared variable
	// $4 must be a Looking Glass statement identifier
	$$ = new LookingGlassCallAst( *$4, $1 );
}
| fn_call {
	$$ = $1;
}
;

/* --------   S t a t e m e n t s   -------- */
  
expr_stmt
: expr {
	$$ = new ListAst($1);
}
| expr_stmt seperators expr {
	$$ = $1->adopt($3);
}
;

eventually_stmt
: "eventually" '(' base_expr ')' "because" stmt_seq "enough" "times" {
	// we implement eventually using 'while not' semantics
	$$ = new EventuallyStatementAst( 
		new UnaryNotOperatorAst($3),
		reinterpret_cast<StatementAst*>($6) );
}
;

term
: seperators {}
;

stmt
: expr_stmt term {
	$$ = $1;
}
| either_expr term {
	$$ = $1;
}
| perhaps_expr term {
	$$ = $1;
}
| eventually_stmt term {
	$$ = $1;
}
;

stmt_seq
: stmt {
	$$ = new ListAst($1);
}
| stmt_seq stmt {
	$$ = $1->adopt($2);
}
;

 /* --------   F u n c t i o n   D e c l e r a t i o n   --------*/

 /* base_expr+ */
fn_parameters
: base_expr {
	// just a single parameter
	$$ = new ListAst($1);
}
| fn_parameters seperators base_expr {
	// append additional parameters in order from left to right
	$$ = $1->adopt($3);
}
;

fn_params_decl
: type_id id {
	$$ = new ListAst(new FunctionParameterAst($1, *$2));
}
| fn_params_decl ',' type_id id {
	$$ = $1->adopt(new FunctionParameterAst($3, *$4));
}
;
  
fn_proto
: "The" "room" id '(' fn_params_decl ')' "contained" "a" type_id {

	// check the name of the parameters
	unordered_set<string> names;
	vector<Ast*>& children = $5->getChildren();
	for (vector<Ast*>::iterator i = children.begin(), e = children.end(); i != e; i++)
	{
		FunctionParameterAst* node = dynamic_cast<FunctionParameterAst*>(*i);
		const string paramName     = node->getName();
		
		if ( names.find( paramName ) == names.end() )
		{
			names.insert( paramName );			
		}
		else 
		{
			// duplicate parameter name!!!
			stringstream ss;
			ss << '\'' << paramName << '\''
			   << " has been used more than once! Ambiguous semantics" << endl;
			$$ = new ErrorAst(ss.str());
			break;
		}
	}

	// if there are n unique parameter names then this proto is valid
	if ( names.size() == children.size() )
	{
		$$ = new FunctionProtoAst(*$3, $9, $5);
	}
}
;

fn_decl
: fn_proto stmt_seq  {

	// check for multiple function definition
	FunctionProtoAst* proto = reinterpret_cast<FunctionProtoAst*>($1);

	Codegen* g         = Codegen::get();
	Module* module     = g->getModule();
	Function* function = module->getFunction(proto->getName());
	if ( function != NULL )
	{
		stringstream ss;
		ss  << "Function " << '\'' << proto->getName() << '\''
			<< " is already defined" << endl;
		$$ = new ErrorAst(ss.str());
	}

	$$ = new FunctionDeclAst(proto, $2);
}
;

looking_glass
: "The" "Looking-Glass" id "changed" "a" type_name stmt_seq {
	$$ = new LookingGlassDeclAst( *$3, new PointerTypeAst(*$6), $7 );
}
;

program_token
: stmt_seq {
	driver.newExpression($1);
}
| fn_decl {
	driver.newFunction($1);
}
| looking_glass {
	driver.newFunction($1);}
;

 /* program_token+ */
program
: program_token {
}
| program program_token {
}
;

%%

void yy::MAliceParser::error(yy::location const& loc, std::string const& msg)
{
	std::cerr << loc << ": " << msg << std::endl;
}

